package two.chapter_1.c1_5;

/**
 * 一次合并操作只可能发送如下两种情况
 * 1，两棵树高度相同，这样合并后新树的高度等于树的高度加1
 * 2，两棵树高度不同，这样合并后新树的高度等于较大那棵树的高度
 * 树高为0 时  触点数为1
 * 两棵树高为0的树合并后高度为1  触点数为2，
 * 由于只有当两棵树高度相同时，新的树高才会加1，
 * 所以树高为1的两棵树合并后高度为2， 触点数为4。
 * 树高为2的两棵树合并后高度为3， 触点数为8。
 *   h=0,k=1
 *   h=1,k=2
 *   h=2,k=4
 *   h=3,k=8
 *   h=4,k=16
 *
 *   ...
 *
 *   k>=2^h  -->  h<=lgk;
 */
public class HeightWeightedQuickUnionUF extends QuickUnionUF {

    private int[] ht;
    public HeightWeightedQuickUnionUF(int N) {
        super(N);
        ht=new int[N];

    }

    @Override
    public void union(int p, int q) {
        int pId=find(p);
        int qId=find(q);
        if (pId!=qId){
            int cmp=ht[pId]-ht[qId];
            if (cmp>0){
                ids[qId]=pId;
            }else if (cmp<0){
                ids[pId]=qId;
            }else {
                ids[qId]=pId;
                //树高加1
                ht[pId]=ht[pId]+1;
            }

            count--;
        }
    }
}
